import java.util.HashMap;
import java.util.Map;

public class Test {
    public static void main(String[] args) {
        /*
        破冰游戏
        class Solution {
    public int iceBreakingGame(int num, int target) {
        int ans = 0;
        //从当还有2个人开始反推
        for(int i = 2; i <= num ; i++) {
            ans = (ans + target) % i;
        }
        return ans;
    }
}
         Z 字形变换
        class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuffer> rows = new ArrayList<>();
        //1.为每层创建一个StringBuffer
        for(int i = 0; i < numRows; i++) {
            rows.add(new StringBuffer());
        }
        int i = 0 , flag = -1;
        //遍历整个字符
        for(char ch : s.toCharArray()) {
            //每一层添加字符
            rows.get(i).append(ch);
            //更新 i 和 flag  当i=0 向下走 i=最后一个位置 向上走
            if(i == 0 || i == numRows - 1) flag = -flag;
            i += flag;
        }
        //进行归总
        StringBuffer ret = new StringBuffer();
        for(StringBuffer row : rows) {
            ret.append(row);
        }
        return ret.toString();
    }
}
         */
        int[] nmus =  {4,5,0,-2,-3,1};
        int count = subarraysDivByK(nmus,5);
        System.out.println(count);
    }

        public static int subarraysDivByK(int[] nums, int k) {
        /*
        前缀和+HashMap+同余定理
        时间复杂度:O(n);空间复杂度O(min(n,k))
        */
            int len = nums.length;
            // 存储结果
            int res = 0;
            // key为前缀和sum[j]对k取模;val统计出现的次数
            // key与真正sum[i-1]相差k的倍数,(sum[j]-sum[i-1])%k==0与(sum[j]-key)%k==0等价
            // 换句话说就是key将前面k=7时,3,10,17,24这类数全部一次性当3统计完次数
            // 下次遇到sum[j]=10,这几个都是合法的sum[i-1],不用一个个去统计了,全部帮你找好了
            Map<Integer, Integer> map = new HashMap<>();
            // 应对前面的数全部都取的情况
            map.put(0, 1);
            // 前缀和
            int sum = 0;
            // 遍历nums数组
            for(int num : nums) {
                // 求[0,j]的前缀和
                sum += num;
                // 这里要格外注意java负数取模的特性:-5%2=-1
                // 负数对正数k取模就是一直+k直到最后一个<=0的数,-5=>-3=>-1
                // 因此针对负数的情况,可以先-5%2=-1,然后再+2=1
                // 此时再对结果取k的模就等于想要的[0,k-1]之间的数了
                int mod = (sum % k + k) % k;
                // 根据同余定理:sum[j]%k==sum[i-1]%k时,sum[i,j]%k==0
                // 举个例子:sum[j]=17,sum[i-1]=10,k=7 17%7=10%7=3
                // 其中sum[j]%k和sum[i-1]%k必定是[0,k-1]的数,若是负数则要一直+k直到范围在[0,k-1]内
                if(map.containsKey(mod)) {
                    res += map.get(mod);
                }
                // 将key为mod对应的值+1
                map.put(mod, map.getOrDefault(mod, 0) + 1);
            }
            return res;
        }
}
